package com.xy6.algo.force;

/**
 * 蛮力法求解背包问题
 * 
 * <pre>
 * 以n=4为例，创建一个v[4]的数组，用0和1表示第i个物品是否放进背包，如0001表示只有第四个物品放进背包。
 * 然后数组从0000~1111，计算每次摆放的重量以及价值。
 * 如果重量小于背包重量，且价值大于当前最大价值，则记录当前的最大价值以及数组。
 * 原理是这样在实施的时候为了记录背包的解，将0000和1111看成0和15的二进制形式，所以让i从0到15进行增长
 * 
 * 时间效率：O((2^n-1)*n)
 * </pre>
 * 
 * @author zhang
 * @since 2017-12-05
 */
public class Package {

	public static void main(String[] args) {
		int v[] = { 0, 10, 25, 40, 20, 10 };
		int w[] = { 0, 40, 50, 70, 40, 20 };
		int total = 120;
		System.out.println(calc(v, w, total));
		
		v = new int[] { 2, 3, 4, 5, 6 };
		w = new int[] { 1, 2, 3, 4, 5 };
		total = 10;
		System.out.println(calc(v, w, total));
	}

	/**
	 * 计算背包能装下物品的最大价值
	 * 
	 * @param weights
	 * @param values
	 * @param max
	 * @return
	 */
	public static int calc(int[] values, int[] weights, int max) {
		int n = weights.length;
		// 2^n - 1。n位二进制1的最大值
		int x = Double.valueOf(Math.pow(2 * 1.0, n * 1.0)).intValue() - 1;
		String binary = null;
		int val = 0;
		int maxVal = 0;
		for (int i = 1; i <= x; i++) {
			binary = convertBin(i, n);
			val = calcVal(values, weights, max, binary);
			if (val > maxVal) {
				maxVal = val;
			}
		}

		return maxVal;
	}

	/**
	 * 将一个数值转换为一个二进制字符串，不足n位，前面补0
	 * 
	 * @param i
	 * @return
	 */
	public static String convertBin(int i, int n) {
		String bin = Integer.toBinaryString(i);
		return String.format("%" + n + "s", bin).replaceAll(" ", "0");
	}

	/**
	 * 当按某个序列放入物品时，计算当前放入背包物品的价值
	 * 
	 * @param weights
	 * @param values
	 * @param max
	 * @param binary
	 * @return
	 */
	private static int calcVal(int[] values, int[] weights, int max, String binary) {
		int v = 0;
		int w = 0;
		for (int i = 0; i < binary.length(); i++) {
			if ("0".equals(String.valueOf(binary.charAt(i)))) {
				continue;
			}
			if (w + weights[i] > max) {
				break;
			}
			w += weights[i];
			v += values[i];
		}
		return v;
	}

}
